﻿//2187. 完成旅途的最少时间
//给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。
//每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。
//给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。



class Solution {
public:
    bool check(vector<int>& time, int totalTrips, long long x)
    {
        long long sum = 0;
        for (auto& e : time)
        {
            sum += x / e;
            if (sum >= totalTrips)
                return true;
        }
        return false;
    }

    long long minimumTime(vector<int>& time, int totalTrips)
    {
        //左右端点
        int m = ranges::max(time);
        //最大时间 total/m+1;
        long long left = 1, right = (totalTrips / time.size() + 1) * m;
        while (left <= right)
        {
            long long mid = (left + right) / 2;
            //满足
            if (check(time, totalTrips, mid))
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return right + 1;
    }
};